﻿\subsection{Counting bits set to 1}

Here is a simple example of a function that calculates the number of bits set in the input value.

This operation is also called \q{population count}\footnote{modern x86 CPUs (supporting SSE4) even have a POPCNT instruction for it}.

\lstinputlisting[style=customc]{patterns/14_bitfields/4_popcnt/shifts.c}

In this loop, the iteration count value $i$ is counting from 0 to 31, 
so the $1 \ll i$ statement is counting from 1 to \TT{0x80000000}.
Describing this operation in natural language, we would say \IT{shift 1 by n bits left}.
In other words, $1 \ll i$ statement consequently produces all possible bit positions in a 32-bit number.
The freed bit at right is always cleared.

\label{2n_numbers_table}
Here is a table of all possible $1 \ll i$ 
for $i=0 \ldots 31$:

\small
\begin{center}
\begin{tabular}{ | l | l | l | l | }
\hline
\HeaderColor \CCpp expression & 
\HeaderColor Power of two & 
\HeaderColor Decimal form & 
\HeaderColor Hexadecimal form \\
\hline
$1 \ll 0$ & 1 & 1 & 1 \\
\hline
$1 \ll 1$ & $2^{1}$ & 2 & 2 \\
\hline
$1 \ll 2$ & $2^{2}$ & 4 & 4 \\
\hline
$1 \ll 3$ & $2^{3}$ & 8 & 8 \\
\hline
$1 \ll 4$ & $2^{4}$ & 16 & 0x10 \\
\hline
$1 \ll 5$ & $2^{5}$ & 32 & 0x20 \\
\hline
$1 \ll 6$ & $2^{6}$ & 64 & 0x40 \\
\hline
$1 \ll 7$ & $2^{7}$ & 128 & 0x80 \\
\hline
$1 \ll 8$ & $2^{8}$ & 256 & 0x100 \\
\hline
$1 \ll 9$ & $2^{9}$ & 512 & 0x200 \\
\hline
$1 \ll 10$ & $2^{10}$ & 1024 & 0x400 \\
\hline
$1 \ll 11$ & $2^{11}$ & 2048 & 0x800 \\
\hline
$1 \ll 12$ & $2^{12}$ & 4096 & 0x1000 \\
\hline
$1 \ll 13$ & $2^{13}$ & 8192 & 0x2000 \\
\hline
$1 \ll 14$ & $2^{14}$ & 16384 & 0x4000 \\
\hline
$1 \ll 15$ & $2^{15}$ & 32768 & 0x8000 \\
\hline
$1 \ll 16$ & $2^{16}$ & 65536 & 0x10000 \\
\hline
$1 \ll 17$ & $2^{17}$ & 131072 & 0x20000 \\
\hline
$1 \ll 18$ & $2^{18}$ & 262144 & 0x40000 \\
\hline
$1 \ll 19$ & $2^{19}$ & 524288 & 0x80000 \\
\hline
$1 \ll 20$ & $2^{20}$ & 1048576 & 0x100000 \\
\hline
$1 \ll 21$ & $2^{21}$ & 2097152 & 0x200000 \\
\hline
$1 \ll 22$ & $2^{22}$ & 4194304 & 0x400000 \\
\hline
$1 \ll 23$ & $2^{23}$ & 8388608 & 0x800000 \\
\hline
$1 \ll 24$ & $2^{24}$ & 16777216 & 0x1000000 \\
\hline
$1 \ll 25$ & $2^{25}$ & 33554432 & 0x2000000 \\
\hline
$1 \ll 26$ & $2^{26}$ & 67108864 & 0x4000000 \\
\hline
$1 \ll 27$ & $2^{27}$ & 134217728 & 0x8000000 \\
\hline
$1 \ll 28$ & $2^{28}$ & 268435456 & 0x10000000 \\
\hline
$1 \ll 29$ & $2^{29}$ & 536870912 & 0x20000000 \\
\hline
$1 \ll 30$ & $2^{30}$ & 1073741824 & 0x40000000 \\
\hline
$1 \ll 31$ & $2^{31}$ & 2147483648 & 0x80000000 \\
\hline
\end{tabular}
\end{center}
\normalsize

These constant numbers (bit masks) very often appear in code and a practicing reverse engineer 
must be able to spot them quickly.

Decimal numbers before 63356 and hecadecimal ones are very easy to memorize.
While decimal numbers after 65536, probably, not worth memorizing.

These constants are very often used for mapping flags to specific bits.
For example, here is excerpt from \TT{ssl\_private.h} 
from Apache 2.4.6 source code:

\begin{lstlisting}[style=customc]
/**
 * Define the SSL options
 */
#define SSL_OPT_NONE           (0)
#define SSL_OPT_RELSET         (1<<0)
#define SSL_OPT_STDENVVARS     (1<<1)
#define SSL_OPT_EXPORTCERTDATA (1<<3)
#define SSL_OPT_FAKEBASICAUTH  (1<<4)
#define SSL_OPT_STRICTREQUIRE  (1<<5)
#define SSL_OPT_OPTRENEGOTIATE (1<<6)
#define SSL_OPT_LEGACYDNFORMAT (1<<7)
\end{lstlisting}

Let's get back to our example.

The \TT{IS\_SET} macro checks bit presence in $a$.
\myindex{x86!\Instructions!AND}

The \TT{IS\_SET} macro is in fact the logical AND operation (\IT{AND}) 
and it returns 0 if the specific bit is absent there,
or the bit mask, if the bit is present.
\IT{The if()} operator in \CCpp triggers if the expression in it is not zero, it might be even 123456, that is why
it always works correctly.

% subsections
\input{patterns/14_bitfields/4_popcnt/x86_EN}
\input{patterns/14_bitfields/4_popcnt/x64_EN}
\input{patterns/14_bitfields/4_popcnt/ARM_EN}
\input{patterns/14_bitfields/4_popcnt/MIPS_EN}
